package com.dxb.test.sort;

/**
 * 计数排序
 * 算法描述
 * 找出待排序的数组中最大和最小的元素；
 * 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 * 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
 * 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
 */
public class CountSort extends BaseSort {
    private int max;
    private int min;

    public CountSort(int[] array) {
        super(array);
        min = max = array[0];
        for (int i = 1; i < length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
    }

    @Override
    public void sort() {
        //存储数组
        int[] temp = new int[length];
        //计数数组
        int[] count = new int[max - min + 1];

        for (int i = 0; i < length; i++) {
            int num = array[i];
            //每出现一个值，计数数组对应元素的值+1
            count[num - min]++;
        }

        for (int num = min + 1; num <= max; num++) {
            //加总数组元素的值为计数数组对应元素及左边所有元素的值的总和
            count[num - min] += count[num - min - 1];
        }

        for (int i = 0; i < length; i++) {
            //源数组第i位的值
            int num = array[i];
            //加总数组中对应元素的下标
            int index = count[num - min] - 1;
            //将该值存入存储数组对应下标中
            temp[index] = num;
            //加总数组中，该值的总和减少1。
            count[num - min]--;
        }

        //将存储数组的值一一替换给源数组
        System.arraycopy(temp, 0, array, 0, length);

    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        BaseSort qs = new CountSort(array);
        qs.run();
    }
}
